/**
 * 673.最长的递增子序列的个数
 */
public class Exerciser3 {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] len = new int[n]; // 以i位置为结尾的最长的递增子序列的长度
        int[] count = new int[n];// 以i位置为结尾的最长的递增子序列的个数
        // 初始化
        for(int i = 0;i < n;i++) {
            len[i] = count[i] = 1;
        }

        int retlen = 1,retcount = 1;
        for(int i = 1;i < n;i++) {
            for(int j = i;j >= 0;j--) {
                if(nums[j] < nums[i]) {
                    if(len[j] + 1 == len[i]) {
                        // 添加个数
                        count[i] += count[j];
                    }else if(len[j] + 1 > len[i]) {
                        // 更新最长的长度，和 对应的最长的个数
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
            // 根据 retlen 和 len[i] 的长度进行更新返回的 retcount的个数
            if(retlen == len[i]) {
                retcount += count[i];
            }else if(retlen < len[i]) {
                retlen = len[i];
                retcount = count[i];
            }
        }
        return retcount;
    }
}
